//x 的平方根   力扣69
//二分查找实现计算x的平方根的整数部分
//需要查找的目标是小于使得mid*mid <= x的最大的mid，因此使用左闭右开的写法时，
//若不能直接查找到，最后left和right会位于刚好大于x的位置上，所以需要减1再返回
class Solution {
public:
	int mySqrt(long long x) {
		long long left = 0;
		long long right = x + 1;
		while(left < right)
		{
			long long mid = left + (right - left) /2;
			if(mid*mid < x) left = mid + 1;
			else if(mid*mid > x) right  = mid;
			else return mid;
		}
		return left - 1;
	}
};
